//
//  ViewController.m
//  Question
//
//  Created by sr Liu on 2020/3/26.
//  Copyright © 2020 sr Liu. All rights reserved.
//

#import "ViewController.h"
#import "StructCusHeader.h"
#import <mach-o/loader.h>

@interface ViewController ()

@end

@implementation ViewController

bool FindNum (int *arr, int columns, int rows, int num);
bool mergeSeqlist (SeqList A, SeqList B, SeqList *C);
bool mergeSeqlistToA (int A[], int B[], int alen, int blen);
BinaryTreeNode * constructCore(int *preOrderStart, int *preOrderEnd, int *inOrderStart, int *inOrderEnd);

- (void)viewDidLoad {
    [super viewDidLoad];
//    NSString *str = @"122";
//    NSString *str1 = @"122";//内存地址一样，常量
    
    
    
}

- (void)touchesBegan:(NSSet<UITouch *> *)touches withEvent:(UIEvent *)event {
    [self toMerge];
}



#pragma mark - 面试题3：二维数组的查找
- (void)toFind {
    int arr[4][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    bool has8 = FindNum(*arr, 4, 4, 8);
    bool has3 = FindNum(*arr, 4, 4, 3);
    NSLog(@"arr has 8 %@", has8 ? @"YES" : @"NO");
    NSLog(@"arr has 3 %@", has3 ? @"YES" : @"NO");
}
/**面试题3
 补上题目和思想
 二维数组，从左到右，从上到下，数字增大
 从中找到一个数字
 右上角开始，往左往下找，所以行增加，列减少
 */
bool FindNum (int *arr, int columns, int rows, int num) {
    bool success = false;
    if (arr != NULL && columns > 0 && rows > 0) {
        int row = 0;
        int column = columns - 1;
        while (row < rows && column >= 0) {
            if (arr[row * column + column] == num) {
                success = true;
                break;
            } else if (arr[row * column + column] > num) {
                column--;
            } else {
                row++;
            }
        }
    }
    
    return success;
}

#pragma mark - 面试题4：替换空格
- (void)toreplace {
    char s[20] = "we are happy.";
    replaceBlank(s, 20);
    NSLog(@"%s",s);
}

/**
面试题4
 //提前计算好替换后的位置
补充
*/
void replaceBlank (char string[], int length) {
    if (string == NULL || length <= 0) {
        return;
    }
    
    int originalLength = 0;
    int blankLength = 0;
    while (string[originalLength] != '\0') {
        originalLength++;//长度14实际最大小标是13
        if (string[originalLength] == ' ' ) {
            blankLength++;
        }
    }
    int newLength = blankLength * 2 + originalLength;
    if (newLength > length) {//不要超过最大空间
        return;
    }
    
    int indexNew = newLength;
    int indexOri = originalLength;
    while (indexNew > indexOri && indexOri >= 0) {
        if (string[indexOri] == ' ') {
            string[indexNew--] = '0';
            string[indexNew--] = '2';
            string[indexNew--] = '%';
        } else {
            string[indexNew--] = string[indexOri];
        }
        indexOri--;
    }
    
}

#pragma mark - 合并两个有序表

- (void)toMerge {
    SeqList *a = (SeqList *)malloc(sizeof(SeqList));
    SeqList *b = (SeqList *)malloc(sizeof(SeqList));
    int adata[] = {1,3,5,7,9};
    int bdata[] = {2,4,6,8,10};
    for (int i = 0; i < 5; i++) {
        a->data[i] = adata[i];
        b->data[i] = bdata[i];
    }
    a->length = 5;
    b->length = 5;
    
    SeqList *c = (SeqList *)malloc(sizeof(SeqList));
    c->length = 20;
    mergeSeqlist(*a, *b, c);
    
    
    int A[20] = {2,4,6,8};
    int B[5] = {1,3,4,5,9};
    mergeSeqlistToA(A, B, 4, 5);
    
}

/**
 两个有序顺序表合成一个新的有序顺序表
 c语言不支持引用传参,（可以用二级指针），不需要改变C，拿到就行了，这里直接用指针
 若要修改C  传入
 SeqList *C; &C传入
 形参是SeqList **C
 */
bool mergeSeqlist (SeqList A, SeqList B, SeqList *C) {
    
    if (A.length + B.length > C->length) {
        return false;
    }
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j]) {
            C->data[k++] = A.data[i++];
        } else {
            C->data[k++] = B.data[j++];
        }
    }
    while (i < A.length) {
        C->data[k++] = A.data[i++];
    }
    while (j < B.length) {
        C->data[k++] = B.data[j++];
    }
    C->length = k;
    
    return true;
}

/**
 A数组足够长，如果把B数组中的内容 都插入到A中并且有序，如何做到最少移动？
 先计算长度从后往前
 */

bool mergeSeqlistToA (int A[], int B[], int alen, int blen) {
    //不判断越界
    int indexNew = alen + blen - 1;
    int indexA = alen - 1;
    int indexB = blen - 1;
    while (indexA >= 0 && indexB >= 0) {
        if (A[indexA] > B[indexB]) {
            A[indexNew--] = A[indexA--];
        } else {
            A[indexNew--] = B[indexB--];
        }
    }
    
    while (indexA >= 0) {
        A[indexNew--] = A[indexA--];
    }
    
    while (indexB >= 0) {
        A[indexNew--] = B[indexB--];
    }
    
    return true;
}

#pragma mark - 链表
//在链表末尾添加一个节点
void addToTail(ListNode **phead, int value) {
    ListNode *pNew = (ListNode *)malloc(sizeof(ListNode));
    pNew->data = value;
    pNew->next = NULL;
    if (*phead == NULL) {
        *phead = pNew;
    } else {
        ListNode *pnode = *phead;
        while (pnode->next != NULL) {
            pnode = pnode->next;
        }
        pnode->next = pNew;
    }
}

//在链表中找到第一个含有某值的节点并删除该节点
void removeNode(ListNode **pHead, int value) {
    if (pHead == NULL || *pHead == NULL) {
        return;
    }
    ListNode *toDeleteNode = NULL;
    if ((*pHead)->data == value) {
        toDeleteNode = *pHead;
        *pHead = (*pHead)->next;
    } else {
        ListNode *pNode = *pHead;
        while (pNode->next != NULL && pNode->next->data != value) {
            pNode = pNode->next;
        }
        if (pNode->next != NULL && pNode->next->data == value) {
            toDeleteNode = pNode->next;
            pNode->next = toDeleteNode->next;
        }
    }
    
    if (toDeleteNode != NULL) {
        free(toDeleteNode);
        toDeleteNode = NULL;
    }
}

#pragma mark - 面试题5：链表翻转

#pragma mark - 面试题6：重建二叉树
/**
 （附带题解中的测试代码是c++的，有点没看懂是怎么printTree的）
 
 使用前序遍历,中序遍历 重建二叉树
 */
- (void)testConstructTree {
    const int length = 8;//不用const数组初始化报错：可能无法初始化
    int preorder[length] = {1,2,4,7,3,5,6,8};
    int inorder[length] = {4,7,2,1,5,3,8,6};
    
    
}

BinaryTreeNode * construct(int *preOrder, int *inOrder, int length) {
    //判空，然后递归构造
    if (preOrder == NULL || inOrder == NULL || length <= 0) {
        return NULL;
    }
    return constructCore(preOrder, preOrder + length - 1, inOrder, inOrder + length - 1);
}

//前序中序的始末位置
BinaryTreeNode * constructCore(int *preOrderStart, int *preOrderEnd, int *inOrderStart, int *inOrderEnd) {
    
    int rootValue = preOrderStart[0];
    BinaryTreeNode *rootNode = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    rootNode->data = rootValue;
    rootNode->leftChild = rootNode->rightChild = NULL;
    
    //最后应该就剩一个
    if (preOrderStart == preOrderEnd) {
        //前序中序始末都一样 数值一样
        if (inOrderStart == inOrderEnd && *preOrderStart == *inOrderStart) {
            return rootNode;
        } else {
            //输入的数有问题
        }
    }
    
    int *inOrderRoot = inOrderStart;
    //要有== 因为end是有值的不是数组个数边界
    while (inOrderStart <= inOrderEnd && *inOrderRoot != rootValue ) {
        inOrderRoot++;
    }
    
    if (inOrderRoot == inOrderEnd && *inOrderRoot != rootValue) {
        //找到最后没有相等的 输入有问题
        return NULL;
    }
    
    long leftTreeLen = inOrderRoot - inOrderStart;
    int *preOrderLeftTreeEnd = preOrderStart + leftTreeLen;
    if (leftTreeLen > 0) {//有左树
        rootNode->leftChild = constructCore(preOrderStart + 1, preOrderLeftTreeEnd, inOrderStart, inOrderRoot - 1);
    }
    if (leftTreeLen < preOrderEnd - preOrderStart) {
        rootNode->rightChild = constructCore(preOrderLeftTreeEnd + 1, preOrderEnd, inOrderRoot + 1, inOrderEnd);
    }
    return NULL;
}


@end
